package monotonousStack

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/src/data_structure/heap_stack_queue/stack"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/28 19:09
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 单调栈【每日温度】
 * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * input:  {73,74,75,71,69,72,76,73}
 * output: {1, 1, 4, 2, 1, 1, 0, 0}
 */
type DailyTemperatures struct {
}

func (m *DailyTemperatures) NextValue(array []int) []int {
	if len(array) < 2 {
		return array
	}
	ans := make([]int, len(array), len(array))
	stacks := stack.ArrayStack{}
	for i := len(array) - 1; i >= 0; i-- {
		for !stacks.Empty() && array[i] >= array[stacks.Peak().(int)] {
			stacks.Pop()
		}
		if stacks.Empty() {
			ans[i] = 0
		} else {
			ans[i] = stacks.Peak().(int) - i
		}
		stacks.Push(i)
	}
	return ans
}
func (m *DailyTemperatures) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.MonotonousStack},
		Desc: &C.Desc{
			Name:   "DailyTemperatures",
			NameCn: "下一日更高的温度:从后往前推",
		},
	}
}
